// 20. 有效的括号
// 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

// 有效字符串需满足：

// 左括号必须用相同类型的右括号闭合。
// 左括号必须以正确的顺序闭合。

// 思路：先分析有几种情况不匹配
// 设置一个栈 存放括号 最后栈为空为真 用map[res]和x比对是否相同 
// 第一种情况：已经遍历完了字符串，但是栈不为空，
// 说明有相应的左括号没有右括号来匹配，所以return false

// 第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false

// 第三种情况：遍历字符串匹配的过程中，栈已经为空了，
// 没有匹配的字符了，说明右括号没有找到对应的左括号return false
/**
 * @param {string} s
 * @return {boolean}
 */
 var isValid = function(s) {
    const res=[];
    const map={
        "(":")",
        "{":"}",
        "[":"]"
    };
    for(const x of s){
        if(x in map){
            res.push(x);
            continue;
        };
        if(map[res.pop()]!==x) return false;
    }
    return !res.length;
};

// 22. 括号生成
// 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

// 输入：n = 3
// 输出：["((()))","(()())","(())()","()(())","()()()"]
// 思路：递归+栈
// 
/**
 * @param {number} n
 * @return {string[]}
 */
 var generateParenthesis = function(n) {
    const res=[];
    const def=(left,right,str)=>{// 左右括号所剩的数量，str是当前构建的字符串
        if(str.length==n*2){// 字符串构建完成
            res.push(str);// 加入解集
            return;// 结束当前递归分支
        }
        if(left>0){// 只要左括号有剩，就可以选它
            def(left-1,right,str+'(');// 然后继续做选择（递归）
        }
        if(right>left){// 右括号比左括号剩的多，才能选右括号
            def(left,right-1,str+')');// 然后继续做选择（递归）
        }
        
        
    }
    def(n,n,'');// 递归的入口，剩余数量都是n，初始字符串是空串
        return res;
};

// 17. 电话号码的字母组合
// 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
// 输入：digits = "23"
// 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
// 思路：回溯+栈
/**
 * @param {string} digits
 * @return {string[]}
 */
 var letterCombinations = function(digits) {
    const res=[];
    const map={"2":'abc',"3":"def","4":"ghi","5":"jkl","6":"mno","7":"pqrs","8":"tuv","9":"wxyz"};
    if(digits.length==0) return res;
    // dfs: 当前构建的字符串为curStr，现在“翻译”到第i个数字，基于此继续“翻译”
    const def=(curstr,i)=>{// curStr是当前字符串，i是扫描的指针
        if(i>digits.length-1){// 指针越界，递归的出口
            res.push(curstr);// 将解推入res
            return; // 结束当前递归分支
        }
        const letters=map[digits[i]];// 当前数字对应的字母
        for(let letter of letters){// 一个字母是一个选择，对应一个递归分支
            def(curstr+letter,i+1);// 选择翻译成letter，生成新字符串，i指针右移继续翻译（递归）
        }
    } 
    def("",0);// 递归的入口，初始字符串为''，从下标0开始翻译
    return res;
};

// 解法二：使用回溯
/**
 * @param {string} digits
 * @return {string[]}
 */
 var letterCombinations = function(digits) {
    const res=[];
    const map = ["","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"];
    let ans=[];
    let len=digits.length;
    if(len===0) return [];
    if(len===1) return map[digits].split("");
    const def=function(digits,len,a){
        if(ans.length==len){
            res.push(ans.join(''));
            return;
        }
        for(let i of map[digits[a]]){// 循环遍历添加 digits的第a位
            ans.push(i);
            def(digits,len,a+1);
            ans.pop();
        }
    }
    def(digits,len,0);
    return res;
};